
#include "Stack.h"
#include <malloc.h>
#include <assert.h>
#include <stdio.h>

void StackInit(Stack* ps)
{
	assert(ps);
	ps->array = (SDataType*)malloc(sizeof(SDataType)* 3);
	if (NULL == ps->array)
	{
		assert(0);
		return;
	}

	ps->capacity = 3;
	ps->size = 0;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	if (ps->array)
	{
		free(ps->array);
		ps->array = NULL;
		ps->capacity = 0;
		ps->size = 0;
	}
}

static void CheckCapacity(Stack* ps)
{
	if (ps->size == ps->capacity)
	{
		// 1. 申请新空间
		int newcapacity = ps->capacity * 2;
		
		//ps->array = (SDataType*)realloc(ps->array, newcapacity);
		SDataType* temp = (SDataType*)malloc(sizeof(SDataType)*newcapacity);
		if (NULL == temp)
		{
			assert(0);
			return;
		}

		// 2. 拷贝元素：将旧空间中的元素拷贝到新空间
		//memcpy(temp, ps->array, sizeof(SDataType)*ps->size);
		for (int i = 0; i < ps->size; ++i)
		{
			temp[i] = ps->array[i];
		}

		// 3. 释放旧空间
		free(ps->array);

		// 4. 使用新空间
		ps->array = temp;
		
		ps->capacity = newcapacity;
	}
}

// 入栈
void StackPush(Stack* ps, SDataType data)
{
	assert(ps);

	CheckCapacity(ps);

	ps->array[ps->size] = data;
	ps->size++;
}


// 出栈
void StackPop(Stack* ps)
{
	if (StackEmpty(ps))
	{
		return;
	}

	ps->size--;
}


// 获取栈顶元素
SDataType StackTop(Stack* ps)
{
	assert(!StackEmpty(ps));
	return ps->array[ps->size-1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->size;
}

// 检测栈是否为空
int StackEmpty(Stack* ps)
{
	assert(ps);
	return 0 == ps->size;
}

////////////////////////////////////////////////////////
void TestStack()
{
	Stack s;
	StackInit(&s);

	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	StackPush(&s, 6);
	StackPush(&s, 7);
	printf("%d\n", StackTop(&s));
	printf("%d\n", StackSize(&s));

	StackPop(&s);
	StackPop(&s);
	StackPop(&s);
	printf("%d\n", StackTop(&s));
	printf("%d\n", StackSize(&s));

	StackDestroy(&s);
}


// 检测data是否在二叉树中
BTNode* Find(BTNode* root, BTDataType data)
{
	